#include"sort.h"
using namespace std;


void bubbleSort(vector<int>& vec) {
	int size = vec.size();
	bool swapped = false;
	for (int i = 0;i < size - 1;++i) {
		swapped = false;
		for (int j = 0; j < size-i-1; j++)
		{
			if (vec[j]>vec[j+1])
			{
				swap(vec[j], vec[j + 1]);
				swapped = true;
			}
		}
		if (!swapped) {
			break;
		}
	}
}



void selectionSort(vector<int>& vec) {
	int size = vec.size();
	for (int i = 0; i < size-1; i++)
	{
		int minPos = i;
		for (int j = i + 1;j < size;++j) {
			if (vec[j] < vec[minPos]) {
				minPos = j;
			}
		}
		if (minPos != i) {
			swap(vec[i], vec[minPos]);
		}
	}



}


void insertionSort(vector<int>& vec) {
	int size = vec.size();
	for (int i = 1;i < size;++i) {
		int key = vec[i];
		int j = i - 1;
		while (j >= 0 && vec[j] > key) {
			vec[j + 1] = vec[j];
			j--;
		}
		vec[j + 1] = key;
	}
}



void shellSort(vector<int>& vec) {
	int size = vec.size();
	for (int gap = size / 2;gap > 0;gap /= 2) {
		for (int i = gap;i < size;++i) {
			int temp = vec[i];
			int j = i - gap;
			while (j >= 0 && vec[j] > temp) {
				vec[j + gap] = vec[j];
				j -= gap;
			}
			vec[j + gap] = temp;
		}
	}
}


void quickSort(std::vector<int>& vec, int left, int right) {
	if (left>= right)
		return;
	int pivot = vec[(left + right) / 2];
	int begin = left - 1, end = right + 1;
	while (true) {
		do {
			begin++;
		} while (vec[begin] < pivot);
		do {
			end -- ;
		} while(vec[end]>pivot);
		if (begin >= end)
			break;
		swap(vec[begin], vec[end]);

	}
	quickSort(vec, left, end);
	quickSort(vec, end + 1, right);
}


void mergeSort(vector<int>& vec, int left, int right) {
	if (left >= right) {
		return;
	}
	int mid = (left + right) / 2;
	mergeSort(vec, left, mid);
	mergeSort(vec, mid + 1, right);

	int k = 0;
	int i = left, j = mid + 1;
	vector<int> tmp;
	while (i <= mid && j <= right) {
		if (vec[i] <= vec[j]) {
			tmp.push_back(vec[i++]);
		}
		else {
			tmp.push_back(vec[j++]);
		}
	}
	while (i <= mid) {
		tmp.push_back(vec[i++]);
	}
	while (j <= right)
	{
		tmp.push_back (vec[j++]);
	}
	for (i = left,k=0; i <= right; i++)
	{
		vec[i] = tmp[k++];
	}
}